package com.banade.learn.algorithm;

import static java.lang.Integer.min;
import static java.lang.Math.max;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * <p>
 * <p>
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Trap {

    /**
     * 算法
     * <p>
     * 初始化 ans=0
     * 从左向右扫描数组：
     * 初始化 \text{max\_left}=0max_left=0 和 \text{max\_right}=0max_right=0
     * 从当前元素向左扫描并更新：
     * \text{max\_left}=\max(\text{max\_left},\text{height}[j])max_left=max(max_left,height[j])
     * 从当前元素向右扫描并更新：
     * \text{max\_right}=\max(\text{max\_right},\text{height}[j])max_right=max(max_right,height[j])
     * 将\min(\text{max\_left},\text{max\_right}) - \text{height}[i]min(max_left,max_right)−height[i] 累加到 \text{ans}ans
     * <p>
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
     * <p>
     * 复杂性分析
     * 时间复杂度： O(n^2)。数组中的每个元素都需要向左向右扫描。
     * 空间复杂度:  O(1) 的额外空间。
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) { //Search the left part for max bar size
                max_left = max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) { //Search the right part for max bar size
                max_right = max(max_right, height[j]);
            }
            ans += min(max_left, max_right) - height[i];
        }
        return ans;
    }

    /**
     * 找到数组中从下标 i 到最左端最高的条形块高度 \text{left\_max}left_max。
     * 找到数组中从下标 i 到最右端最高的条形块高度 \text{right\_max}right_max。
     * 扫描数组 \text{height}height 并更新答案：
     * 累加 \min(\text{max\_left}[i],\text{max\_right}[i]) - \text{height}[i]min(max_left[i],max_right[i])−height[i] 到 ansans 上
     *
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        if (height == null)
            return 0;
        int ans = 0;
        int size = height.length;
        int[] left_max = new int[size], right_max = new int[size];
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
            ans += min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }

    public int trap2(int[] height) {
        int left = 0, right = height.length - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max)
                    left_max = height[left] ;
                else
                    ans += (left_max - height[left]);
                ++left;
            } else {
                if (height[right] >= right_max)
                    right_max = height[right]  ;
                else
                    ans += (right_max - height[right]);
                --right;
            }
        }
        return ans;
    }


}
